package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem52
 * @Description 两个链表的第一个公共节点
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/6 15:22
 * @Version 1.0
 */
public class Problem52 {
    /**
     * 1.使用暴力法
     */

    /**
     * 辅助栈，或者直接得出长度后,  找到第一个相同节点
     */
    LinkNode findFirstCommanNode(LinkNode node1, LinkNode node2) {
        int len1 = getLen(node1);
        int len2 = getLen(node2);

        while (len1 > len2) {
            node1 = node1.next;
            len1--;
        }
        while (len2 > len1) {
            node2 = node2.next;
            len2--;
        }
        while (node1 != null && node2 != null && node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }
    int getLen(LinkNode node) {
        int count = 0;
        while (node != null) {
            node = node.next;
            count++;
        }
        return count;
    }

    /**
     * 双指针法
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode headA_ = headA;
        ListNode headB_ = headB;

        while (headA_ != headB_) {
            headA_ = (headA_ != null)?headA_.next:headB;
            headB_ = (headB_ != null)?headB_.next:headA;
        }
        return headA_;
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode(int v) {
            val = v;
            next = null;
        }
    }

    class LinkNode {
        LinkNode next;
        int val;
    }


    /**
     * 使用递归解决LCA问题：两个二叉树节点的最小公共祖先
     */
    public Node lowestCommonAncestor(Node root, Node p, Node q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }

        Node left = lowestCommonAncestor(root.left, p, q);
        Node right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }


    class Node {
        Node left;
        Node right;
        int val;
    }
}
